//给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。 
//
// 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。 
//
// 你可以认为每种硬币的数量是无限的。 
//
// 
//
// 示例 1： 
//
// 
//输入：coins = [1, 2, 5], amount = 11
//输出：3 
//解释：11 = 5 + 5 + 1 
//
// 示例 2： 
//
// 
//输入：coins = [2], amount = 3
//输出：-1 
//
// 示例 3： 
//
// 
//输入：coins = [1], amount = 0
//输出：0
// 
//
// 示例 4： 
//
// 
//输入：coins = [1], amount = 1
//输出：1
// 
//
// 示例 5： 
//
// 
//输入：coins = [1], amount = 2
//输出：2
// 
//
// 
//
// 提示： 
//
// 
// 1 <= coins.length <= 12 
// 1 <= coins[i] <= 231 - 1 
// 0 <= amount <= 104 
// 
// Related Topics 广度优先搜索 数组 动态规划 
// 👍 1606 👎 0

package com.cute.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CoinChange {
    public static void main(String[] args) {
        Solution solution = new CoinChange().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 动态规划的题目
     * 这是完全背包的问题了
     * dp[i][j] 表示选择到当前硬币价值为j的最小硬币数
     */
    class Solution {
        /**
         * 动态规划，没有考虑完全背包的问题
         * 状态dp[i] 为凑齐总价值为i所需的最小硬币数
         * 状态转移方程dp[amount] = min(dp[amount], 1 + dp[amount - coins[i]]) i遍历所有<=amount的硬币
         * 如果不能凑出来的话需要设置为一个不可出现的值才行，比如amount+1
         * 一维数组就可以解决
         */
        public int coinChange(int[] coins, int amount) {
            int[] dp = new int[amount+1];
            Arrays.fill(dp, amount+1);
            dp[0] = 0;//一枚硬币就能凑出来的时候结果就是1
            for (int i = 1; i <=amount ; i++) {//这里是先遍历的面额
                for (int coin : coins){
                    if (i-coin >= 0 && dp[i-coin]!=amount+1){//这里是在判断i-coin的值是否能凑到
                        dp[i] = Math.min(dp[i],1+dp[i-coin]);
                    }
                }
            }
            return dp[amount] == amount+1 ? -1 : dp[amount];
        }

        /**
         * 完全背包分析：
         * 硬币使用次数不限
         * 硬币总额受到限制
         * 与硬币的组合顺序无关
         * 完全背包问题压缩空间后与背包正好是反的，需要从前向后遍历
         * 先遍历硬币，再遍历金额
         * 手动填表看看过程就清楚了
         *
         *
         * 完全背包和01背包的状态是类似的
         * dp[i][j]表示前i个元素能够得到的最大值为j
         * 状态转移方程为dp[i][j] = max(dp[i-1][j],dp[i-1][j-k*w[i]] + k*v[i]) 其中k>=0且j>=k*w[i]
         * 优化之后的状态转移方程为 dp[i][j] = max(dp[i-1][j],dp[!!! i !!!][j-w[i]]+ v[i])
         * 注意这里max中的值包含上一行和本行的结果
         * 完全背包重点在于遍历每个物品的最大次数
         */
        public int coinChange2(int[] coins, int amount) {
            int[] dp = new int[amount+1];
            Arrays.fill(dp, amount+1);
            dp[0] = 0;
            for (int coin : coins){
                for (int i = coin; i <=amount ; i++) {
                    //压缩到一维必须是从前向后推，因为后边的值需要用到前边的
                    dp[i] = Math.min(dp[i],1+dp[i-coin]);
                }
            }
            return dp[amount] == amount + 1 ? -1 : dp[amount];
        }


        /**
         * 完全背包的二维写法，不进行数组压缩，最朴素的写法
         */
        public int coinChange3(int[] coins, int amount) {
            int len = coins.length;
            int[][] dp = new int[len+1][amount+1];
            Arrays.fill(dp[0], amount+1);
            for (int i = 0; i <= len ; i++) {
                dp[i][0] = 0;
            }
            for (int i = 1 ;i <= len ; i++){
                int coin = coins[i-1];
                for (int j = 1; j <=amount ; j++) {
                    dp[i][j] = dp[i-1][j];
                    for (int k = 1; k*coin <= j ; k++) {//默认情况已经覆盖了k=0了
                        if (dp[i-1][j-k*coin]!=amount+1)
                            dp[i][j] = Math.min(dp[i][j],dp[i-1][j-k*coin]+k);
                    }
                }
            }
            return dp[len][amount] == 0? -1 : dp[len][amount];
        }


        /**
         * 二维数组优化遍历（双重遍历，去掉了k的影响）
         */
        public int coinChange4(int[] coins, int amount) {
            int len = coins.length;
            int[][] dp = new int[len+1][amount+1];
            Arrays.fill(dp[0], amount+1);
            for (int i = 0; i <= len ; i++) {
                dp[i][0] = 0;
            }
            for (int i = 1 ;i <= len ; i++){
                int coin = coins[i-1];
                for (int j = 1; j <=amount ; j++) {
                    dp[i][j] = dp[i-1][j];//这里一定要有才行
                    if (j-coin>=0)//注意这里是i不是i-1了，所以压缩成一维之后要从前向后遍历
                        dp[i][j] = Math.min(dp[i][j],dp[i][j-coin]+1);
                }
            }
            return dp[len][amount] == 0? -1 : dp[len][amount];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

    /*if (amount == 0 )return 0;
            if (coins.length == 1) return amount%coins[0]==0 ? amount/coins[0] : -1;
            Arrays.sort(coins);
            if (coins[0]>amount) return -1;
            int len = coins.length;
            int[][] dp = new int[len+1][amount+1];
            for (int i = 1; i <= len ; i++) {
                int value = coins[i-1];
                for (int j = 0; j <= amount ; j++) {
                    if (value<=amount) {
                        if (j<value){
                            dp[i][j] = dp[i-1][j];
                        }else if (j == value) dp[i][j] = 1;
                        else {
                            int dif = j % value;
                            dp[i][j] = dp[i-1][dif] + j/value;
                        }
                    }else{
                        int dif = amount % coins[i-2];
                        dp[i][j] = dp[i-1][dif] + amount/coins[i-2];
                    }
                }
            }
            return dp[len][amount]==0?-1:dp[len][amount];*/

}